package com.note.feng.leetcode.algorithms.easy;

public class HundredTwentyFive {

    /**
     * 125 验证回文串
     * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
     *
     * 说明：本题中，我们将空字符串定义为有效的回文串。
     *
     * 示例 1:
     *
     * 输入: "A man, a plan, a canal: Panama"
     * 输出: true
     * 解释："amanaplanacanalpanama" 是回文串
     * 示例 2:
     *
     * 输入: "race a car"
     * 输出: false
     * 解释："raceacar" 不是回文串
     *
     * 提示：
     *
     * 1 <= s.length <= 2 * 105
     * 字符串 s 由 ASCII 字符组成
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/valid-palindrome
     */
    /**
     *解法：
     * 双指针遍历：
     * 左右指针分别指向字符串的两端，首先要判断指针当前指向的字符是否是字母或数字，
     * 1、是字母或数字，比较两个字符是否相同
     * 2、不是字母或数字，左指针右移，右指针左移，直到是字母或数字为止
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right){
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))){
                left ++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))){
                right --;
            }
            if(left < right){
                if(Character.toLowerCase(s.charAt(left ++)) != Character.toLowerCase(s.charAt(right --))){
                    return false;
                }
            }
        }
        return true;
    }
}
